Physicist Robert Geroch is most known for his work on general relativity, Einstein's theory of gravity. A few years ago, however, he taught a course on the theory of computation: what are the fundamental limits on various types of computers, and how fast can they solve various problems? His lecture notes have been turned into an excellent little book, Perspectives in Computation. It's far from easy material, and (as with Keith Devlin's Joy of Sets text on set theory) I found myself reading and re-reading early chapters, then skimming later ones. Geroch's treatment is highly mathematical, but grounded in practicality. It's also chatty, with humorous asides, e.g.:

• "I feel that it might be enlightening to carry out this strategy—but it looks like a lot of work."
• "Embarrassingly enough, we do not understand even this simple little problem well enough to generate from it an actual counterexample to this conjecture!"
• "We shall simply ignore the effects of errors, not out of any conviction these effects are likely to be unimportant, but rather because we do not know how to do anything else."

Geroch's big accomplishment is to shine light on specific areas of the mathematics of computing. He develops plausible measures for computational difficulty and applies them to classical, probabilistic, and quantum computers. The startling conclusion, stated at the end of the Introduction:

We have today not one single example of a problem, together with a quantum-assisted computation of that problem, such that we can actually prove that at least the same efficiency cannot be achieved already without using quantum mechanics.

This, in spite of the apparent radical benefits of quantum mechanical processes for doing what seem to be extraordinary massively parallel computations. The bulk of Geroch's book is devoted to exploring the issue. He ends the Conclusion with a far-out speculation: "Can one, for example, imagine a plausible-looking physical theory within whose framework certain computations can be speeded up even more dramatically?" That is, if quantum mechanics offers magic, might there be something else with even more power? What in the world could that be?

^z - 2010-09-16